The present invention relates to the determination of routes by a vehicle navigation system. More specifically, the invention provides various methods and apparatus for efficiently determining an optimal route to a user's final destination. According to various embodiments of the invention, the user may begin driving before the entire route to the final destination has been determined due to the generation of one or more intermediate routes. In addition, the present invention provides methods and apparatus for quickly generating an optimal route to the final destination, "seaming" the optimal route with the intermediate route, and determining a termination point for the intermediate route. Also described herein is a method and apparatus for optimizing route generation in a grid pattern region.
As the coverage and feature density of available map databases increase, the time required for the generation of long distance routes has correlatively increased. For particularly long or complex routes, undesirable delays may be experienced before the user may leave her initial location. If the user decides to leave before the route has been generated, she will be operating without instructions from the navigation system and will likely depart from the eventually generated route, thereby rendering the route generation useless. The above-described effects of long route generation time could be mitigated if there were a way in which the first few instructions or maneuvers could be determined and communicated to the user before the entire route generation is complete.
In addition, because the time required for route generation is so long, it is desirable to provide alternatives to current route generation methods which reduce this overhead. To determine a route to a destination, currently available vehicle navigation systems typically employ a search algorithm based on the well known artificial intelligence (AI) graph search technique referred to as "A*". A* is described in Principle of Artificial Intelligence, Nilsson, Nils J., 1993; ISBN 0-934613-10-9, which is incorporated herein by reference. In general, A* performs a directed, breadth-first search through the graph, i.e., map database, from the source to the destination, building a tree of possible solution paths as it progresses, the root of the tree being the source segment. The A* algorithms iterates by determining all of the nearest connected segments to each "branch" or tree segment beginning with the source segment. A cost (f(n)) for each segment is then determined according to the formula EQU f(n)=g(n)+h(n) (1)
with g(n) representing the known cost from the source segment to segment n, and h(n) representing the heuristic cost from segment n to the destination. The heuristic cost is essentially an intelligent guess of the actual cost from segment n to the destination. The segment with the lowest overall cost is then selected as part of the route and the algorithm continues until a segment corresponding to the desired destination is selected. The use of the cost formula in equation (1) has the effect of progressively narrowing the search area toward the destination. However, because the route generation times using the unmodified A* algorithm are still fairly long, it remains desirable to provide route generation solutions which mitigate the undesirable effects of this overhead.